home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / network / manageme / tcpdump-.7 / tcpdump- / tcpdump-richard-1.7 / libpcap-0.0 / optimize.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-12  |  37.8 KB  |  1,926 lines
  1. /*
  2.  * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that: (1) source code distributions
  7.  * retain the above copyright notice and this paragraph in its entirety, (2)
  8.  * distributions including binary code include the above copyright notice and
  9.  * this paragraph in its entirety in the documentation or other materials
  10.  * provided with the distribution, and (3) all advertising materials mentioning
  11.  * features or use of this software display the following acknowledgement:
  12.  * ``This product includes software developed by the University of California,
  13.  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14.  * the University nor the names of its contributors may be used to endorse
  15.  * or promote products derived from this software without specific prior
  16.  * written permission.
  17.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20.  *
  21.  *  Optimization module for tcpdump intermediate representation.
  22.  */
  23. #ifndef lint
  24. static char rcsid[] =
  25.     "@(#) $Header: optimize.c,v 1.45 94/06/20 19:07:55 leres Exp $ (LBL)";
  26. #endif
  27.  
  28. #include <sys/types.h>
  29. #include <sys/time.h>
  30.  
  31. #include <net/bpf.h>
  32.  
  33. #include <stdio.h>
  34. #if __STDC__
  35. #include <stdlib.h>
  36. #endif
  37. #ifdef __osf__
  38. #include <malloc.h>
  39. #endif
  40. #include <memory.h>
  41.  
  42. #include "gencode.h"
  43.  
  44. #ifndef __GNUC__
  45. #define inline
  46. #endif
  47.  
  48. #define A_ATOM BPF_MEMWORDS
  49. #define X_ATOM (BPF_MEMWORDS+1)
  50.  
  51. #define NOP -1
  52.  
  53. /*
  54.  * This define is used to represent *both* the accumulator and
  55.  * x register in use-def computations.
  56.  * Currently, the use-def code assumes only one definition per instruction.
  57.  */
  58. #define AX_ATOM N_ATOMS
  59.  
  60. /*
  61.  * A flag to indicate that further optimization is needed.
  62.  * Iterative passes are continued until a given pass yields no
  63.  * branch movement.
  64.  */
  65. static int done;
  66.  
  67. /*
  68.  * A block is marked if only if its mark equals the current mark.
  69.  * Rather than traverse the code array, marking each item, 'cur_mark' is
  70.  * incremented.  This automatically makes each element unmarked.
  71.  */
  72. static int cur_mark;
  73. #define isMarked(p) ((p)->mark == cur_mark)
  74. #define unMarkAll() cur_mark += 1
  75. #define Mark(p) ((p)->mark = cur_mark)
  76.  
  77. static void opt_init(struct block *);
  78. static void opt_cleanup(void);
  79.  
  80. static void make_marks(struct block *);
  81. static void mark_code(struct block *);
  82.  
  83. static void intern_blocks(struct block *);
  84.  
  85. static int eq_slist(struct slist *, struct slist *);
  86.  
  87. static void find_levels_r(struct block *);
  88.  
  89. static void find_levels(struct block *);
  90. static void find_dom(struct block *);
  91. static void propedom(struct edge *);
  92. static void find_edom(struct block *);
  93. static void find_closure(struct block *);
  94. static int atomuse(struct stmt *);
  95. static int atomdef(struct stmt *);
  96. static void compute_local_ud(struct block *);
  97. static void find_ud(struct block *);
  98. static void init_val(void);
  99. static long F(int, long, long);
  100. static inline void vstore(struct stmt *, long *, long, int);
  101. static void opt_blk(struct block *, int);
  102. static int use_conflict(struct block *, struct block *);
  103. static void opt_j(struct edge *);
  104. static void or_pullup(struct block *);
  105. static void and_pullup(struct block *);
  106. static void opt_blks(struct block *, int);
  107. static inline void link_inedge(struct edge *, struct block *);
  108. static void find_inedges(struct block *);
  109. static void opt_root(struct block **);
  110. static void opt_loop(struct block *, int);
  111. static void fold_op(struct stmt *, long, long);
  112. static inline struct slist *this_op(struct slist *);
  113. static void opt_not(struct block *);
  114. static void opt_peep(struct block *);
  115. static void opt_stmt(struct stmt *, long[], int);
  116. static void deadstmt(struct stmt *, struct stmt *[]);
  117. static void opt_deadstores(struct block *);
  118. static void opt_blk(struct block *, int);
  119. static int use_conflict(struct block *, struct block *);
  120. static void opt_j(struct edge *);
  121. static struct block *fold_edge(struct block *, struct edge *);
  122. static inline int eq_blk(struct block *, struct block *);
  123. static int slength(struct slist *);
  124. static int count_blocks(struct block *);
  125. static void number_blks_r(struct block *);
  126. static int count_stmts(struct block *);
  127. static void convert_code_r(struct block *);
  128.  
  129. static int n_blocks;
  130. struct block **blocks;
  131. static int n_edges;
  132. struct edge **edges;
  133.  
  134. /*
  135.  * A bit vector set representation of the dominators.
  136.  * We round up the set size to the next power of two.
  137.  */
  138. static int nodewords;
  139. static int edgewords;
  140. struct block **levels;
  141. u_long *space;
  142. #define BITS_PER_WORD (8*sizeof(u_long))
  143. /*
  144.  * True if a is in uset {p}
  145.  */
  146. #define SET_MEMBER(p, a) \
  147. ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD)))
  148.  
  149. /*
  150.  * Add 'a' to uset p.
  151.  */
  152. #define SET_INSERT(p, a) \
  153. (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD))
  154.  
  155. /*
  156.  * Delete 'a' from uset p.
  157.  */
  158. #define SET_DELETE(p, a) \
  159. (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD))
  160.  
  161. /*
  162.  * a := a intersect b
  163.  */
  164. #define SET_INTERSECT(a, b, n)\
  165. {\
  166.     register u_long *_x = a, *_y = b;\
  167.     register int _n = n;\
  168.     while (--_n >= 0) *_x++ &= *_y++;\
  169. }
  170.  
  171. /*
  172.  * a := a - b
  173.  */
  174. #define SET_SUBTRACT(a, b, n)\
  175. {\
  176.     register u_long *_x = a, *_y = b;\
  177.     register int _n = n;\
  178.     while (--_n >= 0) *_x++ &=~ *_y++;\
  179. }
  180.  
  181. /*
  182.  * a := a union b
  183.  */
  184. #define SET_UNION(a, b, n)\
  185. {\
  186.     register u_long *_x = a, *_y = b;\
  187.     register int _n = n;\
  188.     while (--_n >= 0) *_x++ |= *_y++;\
  189. }
  190.  
  191. static uset all_dom_sets;
  192. static uset all_closure_sets;
  193. static uset all_edge_sets;
  194.  
  195. #ifndef MAX
  196. #define MAX(a,b) ((a)>(b)?(a):(b))
  197. #endif
  198.  
  199. static void
  200. find_levels_r(b)
  201.     struct block *b;
  202. {
  203.     int level;
  204.  
  205.     if (isMarked(b))
  206.         return;
  207.  
  208.     Mark(b);
  209.     b->link = 0;
  210.  
  211.     if (JT(b)) {
  212.         find_levels_r(JT(b));
  213.         find_levels_r(JF(b));
  214.         level = MAX(JT(b)->level, JF(b)->level) + 1;
  215.     } else
  216.         level = 0;
  217.     b->level = level;
  218.     b->link = levels[level];
  219.     levels[level] = b;
  220. }
  221.  
  222. /*
  223.  * Level graph.  The levels go from 0 at the leaves to
  224.  * N_LEVELS at the root.  The levels[] array points to the
  225.  * first node of the level list, whose elements are linked
  226.  * with the 'link' field of the struct block.
  227.  */
  228. static void
  229. find_levels(root)
  230.     struct block *root;
  231. {
  232.     memset((char *)levels, 0, n_blocks * sizeof(*levels));
  233.     unMarkAll();
  234.     find_levels_r(root);
  235. }
  236.  
  237. /*
  238.  * Find dominator relationships.
  239.  * Assumes graph has been leveled.
  240.  */
  241. static void
  242. find_dom(root)
  243.     struct block *root;
  244. {
  245.     int i;
  246.     struct block *b;
  247.     u_long *x;
  248.  
  249.     /*
  250.      * Initialize sets to contain all nodes.
  251.      */
  252.     x = all_dom_sets;
  253.     i = n_blocks * nodewords;
  254.     while (--i >= 0)
  255.         *x++ = ~0;
  256.     /* Root starts off empty. */
  257.     for (i = nodewords; --i >= 0;)
  258.         root->dom[i] = 0;
  259.  
  260.     /* root->level is the highest level no found. */
  261.     for (i = root->level; i >= 0; --i) {
  262.         for (b = levels[i]; b; b = b->link) {
  263.             SET_INSERT(b->dom, b->id);
  264.             if (JT(b) == 0)
  265.                 continue;
  266.             SET_INTERSECT(JT(b)->dom, b->dom, nodewords);
  267.             SET_INTERSECT(JF(b)->dom, b->dom, nodewords);
  268.         }
  269.     }
  270. }
  271.  
  272. static void
  273. propedom(ep)
  274.     struct edge *ep;
  275. {
  276.     SET_INSERT(ep->edom, ep->id);
  277.     if (ep->succ) {
  278.         SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords);
  279.         SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords);
  280.     }
  281. }
  282.  
  283. /*
  284.  * Compute edge dominators.
  285.  * Assumes graph has been leveled and predecessors established.
  286.  */
  287. static void
  288. find_edom(root)
  289.     struct block *root;
  290. {
  291.     int i;
  292.     uset x;
  293.     struct block *b;
  294.  
  295.     x = all_edge_sets;
  296.     for (i = n_edges * edgewords; --i >= 0; )
  297.         x[i] = ~0;
  298.  
  299.     /* root->level is the highest level no found. */
  300.     memset(root->et.edom, 0, edgewords * sizeof(*(uset)0));
  301.     memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0));
  302.     for (i = root->level; i >= 0; --i) {
  303.         for (b = levels[i]; b != 0; b = b->link) {
  304.             propedom(&b->et);
  305.             propedom(&b->ef);
  306.         }
  307.     }
  308. }
  309.  
  310. /*
  311.  * Find the backwards transitive closure of the flow graph.  These sets
  312.  * are backwards in the sense that we find the set of nodes that reach
  313.  * a given node, not the set of nodes that can be reached by a node.
  314.  *
  315.  * Assumes graph has been leveled.
  316.  */
  317. static void
  318. find_closure(root)
  319.     struct block *root;
  320. {
  321.     int i;
  322.     struct block *b;
  323.  
  324.     /*
  325.      * Initialize sets to contain no nodes.
  326.      */
  327.     memset((char *)all_closure_sets, 0,
  328.           n_blocks * nodewords * sizeof(*all_closure_sets));
  329.  
  330.     /* root->level is the highest level no found. */
  331.     for (i = root->level; i >= 0; --i) {
  332.         for (b = levels[i]; b; b = b->link) {
  333.             SET_INSERT(b->closure, b->id);
  334.             if (JT(b) == 0)
  335.                 continue;
  336.             SET_UNION(JT(b)->closure, b->closure, nodewords);
  337.             SET_UNION(JF(b)->closure, b->closure, nodewords);
  338.         }
  339.     }
  340. }
  341.  
  342. /*
  343.  * Return the register number that is used by s.  If A and X are both
  344.  * used, return AX_ATOM.  If no register is used, return -1.
  345.  *
  346.  * The implementation should probably change to an array access.
  347.  */
  348. static int
  349. atomuse(s)
  350.     struct stmt *s;
  351. {
  352.     register int c = s->code;
  353.  
  354.     if (c == NOP)
  355.         return -1;
  356.  
  357.     switch (BPF_CLASS(c)) {
  358.  
  359.     case BPF_RET:
  360.         return (BPF_RVAL(c) == BPF_A) ? A_ATOM :
  361.             (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;
  362.  
  363.     case BPF_LD:
  364.     case BPF_LDX:
  365.         return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
  366.             (BPF_MODE(c) == BPF_MEM) ? s->k : -1;
  367.  
  368.     case BPF_ST:
  369.         return A_ATOM;
  370.  
  371.     case BPF_STX:
  372.         return X_ATOM;
  373.  
  374.     case BPF_JMP:
  375.     case BPF_ALU:
  376.         if (BPF_SRC(c) == BPF_X)
  377.             return AX_ATOM;
  378.         return A_ATOM;
  379.  
  380.     case BPF_MISC:
  381.         return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
  382.     }
  383.     abort();
  384.     /* NOTREACHED */
  385. }
  386.  
  387. /*
  388.  * Return the register number that is defined by 's'.  We assume that
  389.  * a single stmt cannot define more than one register.  If no register
  390.  * is defined, return -1.
  391.  *
  392.  * The implementation should probably change to an array access.
  393.  */
  394. static int
  395. atomdef(s)
  396.     struct stmt *s;
  397. {
  398.     if (s->code == NOP)
  399.         return -1;
  400.  
  401.     switch (BPF_CLASS(s->code)) {
  402.  
  403.     case BPF_LD:
  404.     case BPF_ALU:
  405.         return A_ATOM;
  406.  
  407.     case BPF_LDX:
  408.         return X_ATOM;
  409.  
  410.     case BPF_ST:
  411.     case BPF_STX:
  412.         return s->k;
  413.  
  414.     case BPF_MISC:
  415.         return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
  416.     }
  417.     return -1;
  418. }
  419.  
  420. static void
  421. compute_local_ud(b)
  422.     struct block *b;
  423. {
  424.     struct slist *s;
  425.     atomset def = 0, use = 0, kill = 0;
  426.     int atom;
  427.  
  428.     for (s = b->stmts; s; s = s->next) {
  429.         if (s->s.code == NOP)
  430.             continue;
  431.         atom = atomuse(&s->s);
  432.         if (atom >= 0) {
  433.             if (atom == AX_ATOM) {
  434.                 if (!ATOMELEM(def, X_ATOM))
  435.                     use |= ATOMMASK(X_ATOM);
  436.                 if (!ATOMELEM(def, A_ATOM))
  437.                     use |= ATOMMASK(A_ATOM);
  438.             }
  439.             else if (atom < N_ATOMS) {
  440.                 if (!ATOMELEM(def, atom))
  441.                     use |= ATOMMASK(atom);
  442.             }
  443.             else
  444.                 abort();
  445.         }
  446.         atom = atomdef(&s->s);
  447.         if (atom >= 0) {
  448.             if (!ATOMELEM(use, atom))
  449.                 kill |= ATOMMASK(atom);
  450.             def |= ATOMMASK(atom);
  451.         }
  452.     }
  453.     if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP)
  454.         use |= ATOMMASK(A_ATOM);
  455.  
  456.     b->def = def;
  457.     b->kill = kill;
  458.     b->in_use = use;
  459. }
  460.  
  461. /*
  462.  * Assume graph is already leveled.
  463.  */
  464. static void
  465. find_ud(root)
  466.     struct block *root;
  467. {
  468.     int i, maxlevel;
  469.     struct block *p;
  470.  
  471.     /*
  472.      * root->level is the highest level no found;
  473.      * count down from there.
  474.      */
  475.     maxlevel = root->level;
  476.     for (i = maxlevel; i >= 0; --i)
  477.         for (p = levels[i]; p; p = p->link) {
  478.             compute_local_ud(p);
  479.             p->out_use = 0;
  480.         }
  481.  
  482.     for (i = 1; i <= maxlevel; ++i) {
  483.         for (p = levels[i]; p; p = p->link) {
  484.             p->out_use |= JT(p)->in_use | JF(p)->in_use;
  485.             p->in_use |= p->out_use &~ p->kill;
  486.         }
  487.     }
  488. }
  489.  
  490. /*
  491.  * These data structures are used in a Cocke and Shwarz style
  492.  * value numbering scheme.  Since the flowgraph is acyclic,
  493.  * exit values can be propagated from a node's predecessors
  494.  * provided it is uniquely defined.
  495.  */
  496. struct valnode {
  497.     int code;
  498.     long v0, v1;
  499.     long val;
  500.     struct valnode *next;
  501. };
  502.  
  503. #define MODULUS 213
  504. static struct valnode *hashtbl[MODULUS];
  505. static int curval;
  506. static int maxval;
  507.  
  508. /* Integer constants mapped with the load immediate opcode. */
  509. #define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L)
  510.  
  511. struct vmapinfo {
  512.     int is_const;
  513.     long const_val;
  514. };
  515.  
  516. struct vmapinfo *vmap;
  517. struct valnode *vnode_base;
  518. struct valnode *next_vnode;
  519.  
  520. static void
  521. init_val()
  522. {
  523.     curval = 0;
  524.     next_vnode = vnode_base;
  525.     memset((char *)vmap, 0, maxval * sizeof(*vmap));
  526.     memset((char *)hashtbl, 0, sizeof hashtbl);
  527. }
  528.  
  529. /* Because we really don't have an IR, this stuff is a little messy. */
  530. static long
  531. F(code, v0, v1)
  532.     int code;
  533.     long v0, v1;
  534. {
  535.     u_int hash;
  536.     int val;
  537.     struct valnode *p;
  538.  
  539.     hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8);
  540.     hash %= MODULUS;
  541.  
  542.     for (p = hashtbl[hash]; p; p = p->next)
  543.         if (p->code == code && p->v0 == v0 && p->v1 == v1)
  544.             return p->val;
  545.  
  546.     val = ++curval;
  547.     if (BPF_MODE(code) == BPF_IMM &&
  548.         (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
  549.         vmap[val].const_val = v0;
  550.         vmap[val].is_const = 1;
  551.     }
  552.     p = next_vnode++;
  553.     p->val = val;
  554.     p->code = code;
  555.     p->v0 = v0;
  556.     p->v1 = v1;
  557.     p->next = hashtbl[hash];
  558.     hashtbl[hash] = p;
  559.  
  560.     return val;
  561. }
  562.  
  563. static inline void
  564. vstore(s, valp, newval, alter)
  565.     struct stmt *s;
  566.     long *valp;
  567.     long newval;
  568.     int alter;
  569. {
  570.     if (alter && *valp == newval)
  571.         s->code = NOP;
  572.     else
  573.         *valp = newval;
  574. }
  575.  
  576. static void
  577. fold_op(s, v0, v1)
  578.     struct stmt *s;
  579.     long v0, v1;
  580. {
  581.     long a, b;
  582.  
  583.     a = vmap[v0].const_val;
  584.     b = vmap[v1].const_val;
  585.  
  586.     switch (BPF_OP(s->code)) {
  587.     case BPF_ADD:
  588.         a += b;
  589.         break;
  590.  
  591.     case BPF_SUB:
  592.         a -= b;
  593.         break;
  594.  
  595.     case BPF_MUL:
  596.         a *= b;
  597.         break;
  598.  
  599.     case BPF_DIV:
  600.         if (b == 0)
  601.             bpf_error("division by zero");
  602.         a /= b;
  603.         break;
  604.  
  605.     case BPF_AND:
  606.         a &= b;
  607.         break;
  608.  
  609.     case BPF_OR:
  610.         a |= b;
  611.         break;
  612.  
  613.     case BPF_LSH:
  614.         a <<= b;
  615.         break;
  616.  
  617.     case BPF_RSH:
  618.         a >>= b;
  619.         break;
  620.  
  621.     case BPF_NEG:
  622.         a = -a;
  623.         break;
  624.  
  625.     default:
  626.         abort();
  627.     }
  628.     s->k = a;
  629.     s->code = BPF_LD|BPF_IMM;
  630.     done = 0;
  631. }
  632.  
  633. static inline struct slist *
  634. this_op(s)
  635.     struct slist *s;
  636. {
  637.     while (s != 0 && s->s.code == NOP)
  638.         s = s->next;
  639.     return s;
  640. }
  641.  
  642. static void
  643. opt_not(b)
  644.     struct block *b;
  645. {
  646.     struct block *tmp = JT(b);
  647.  
  648.     JT(b) = JF(b);
  649.     JF(b) = tmp;
  650. }
  651.  
  652. static void
  653. opt_peep(b)
  654.     struct block *b;
  655. {
  656.     struct slist *s;
  657.     struct slist *next, *last;
  658.     int val;
  659.     long v;
  660.  
  661.     s = b->stmts;
  662.     if (s == 0)
  663.         return;
  664.  
  665.     last = s;
  666.     while (1) {
  667.         s = this_op(s);
  668.         if (s == 0)
  669.             break;
  670.         next = this_op(s->next);
  671.         if (next == 0)
  672.             break;
  673.         last = next;
  674.  
  675.         /*
  676.          * st  M[k]    -->    st  M[k]
  677.          * ldx M[k]        tax
  678.          */
  679.         if (s->s.code == BPF_ST &&
  680.             next->s.code == (BPF_LDX|BPF_MEM) &&
  681.             s->s.k == next->s.k) {
  682.             done = 0;
  683.             next->s.code = BPF_MISC|BPF_TAX;
  684.         }
  685.         /*
  686.          * ld  #k    -->    ldx  #k
  687.          * tax            txa
  688.          */
  689.         if (s->s.code == (BPF_LD|BPF_IMM) &&
  690.             next->s.code == (BPF_MISC|BPF_TAX)) {
  691.             s->s.code = BPF_LDX|BPF_IMM;
  692.             next->s.code = BPF_MISC|BPF_TXA;
  693.             done = 0;
  694.         }
  695.         /*
  696.          * This is an ugly special case, but it happens
  697.          * when you say tcp[k] or udp[k] where k is a constant.
  698.          */
  699.         if (s->s.code == (BPF_LD|BPF_IMM)) {
  700.             struct slist *add, *tax, *ild;
  701.  
  702.             /*
  703.              * Check that X isn't used on exit from this
  704.              * block (which the optimizer might cause).
  705.              * We know the code generator won't generate
  706.              * any local dependencies.
  707.              */
  708.             if (ATOMELEM(b->out_use, X_ATOM))
  709.                 break;
  710.  
  711.             if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
  712.                 add = next;
  713.             else
  714.                 add = this_op(next->next);
  715.             if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
  716.                 break;
  717.  
  718.             tax = this_op(add->next);
  719.             if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
  720.                 break;
  721.  
  722.             ild = this_op(tax->next);
  723.             if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
  724.                 BPF_MODE(ild->s.code) != BPF_IND)
  725.                 break;
  726.             /*
  727.              * XXX We need to check that X is not
  728.              * subsequently used.  We know we can eliminate the
  729.              * accumulator modifications since it is defined
  730.              * by the last stmt of this sequence.
  731.              *
  732.              * We want to turn this sequence:
  733.              *
  734.              * (004) ldi     #0x2        {s}
  735.              * (005) ldxms   [14]        {next}  -- optional
  736.              * (006) addx            {add}
  737.              * (007) tax            {tax}
  738.              * (008) ild     [x+0]        {ild}
  739.              *
  740.              * into this sequence:
  741.              *
  742.              * (004) nop
  743.              * (005) ldxms   [14]
  744.              * (006) nop
  745.              * (007) nop
  746.              * (008) ild     [x+2]
  747.              *
  748.              */
  749.             ild->s.k += s->s.k;
  750.             s->s.code = NOP;
  751.             add->s.code = NOP;
  752.             tax->s.code = NOP;
  753.             done = 0;
  754.         }
  755.         s = next;
  756.     }
  757.     /*
  758.      * If we have a subtract to do a comparison, and the X register
  759.      * is a known constant, we can merge this value into the
  760.      * comparison.
  761.      */
  762.     if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
  763.         !ATOMELEM(b->out_use, A_ATOM)) {
  764.         val = b->val[X_ATOM];
  765.         if (vmap[val].is_const) {
  766.             b->s.k += vmap[val].const_val;
  767.             last->s.code = NOP;
  768.             done = 0;
  769.         } else if (b->s.k == 0) {
  770.             /*
  771.              * sub x  ->    nop
  772.              * j  #0    j  x
  773.              */
  774.             last->s.code = NOP;
  775.             b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) |
  776.                 BPF_X;
  777.             done = 0;
  778.         }
  779.     }
  780.     /*
  781.      * Likewise, a constant subtract can be simplified.
  782.      */
  783.     else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
  784.          !ATOMELEM(b->out_use, A_ATOM)) {
  785.         b->s.k += last->s.k;
  786.         last->s.code = NOP;
  787.         done = 0;
  788.     }
  789.     /*
  790.      * and #k    nop
  791.      * jeq #0  ->    jset #k
  792.      */
  793.     if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) &&
  794.         !ATOMELEM(b->out_use, A_ATOM) && b->s.k == 0) {
  795.         b->s.k = last->s.k;
  796.         b->s.code = BPF_JMP|BPF_K|BPF_JSET;
  797.         last->s.code = NOP;
  798.         done = 0;
  799.         opt_not(b);
  800.     }
  801.     /*
  802.      * If the accumulator is a known constant, we can compute the
  803.      * comparison result.
  804.      */
  805.     val = b->val[A_ATOM];
  806.     if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
  807.         v = vmap[val].const_val;
  808.         switch (BPF_OP(b->s.code)) {
  809.  
  810.         case BPF_JEQ:
  811.             v = v == b->s.k;
  812.             break;
  813.  
  814.         case BPF_JGT:
  815.             v = v > b->s.k;
  816.             break;
  817.  
  818.         case BPF_JGE:
  819.             v = v >= b->s.k;
  820.             break;
  821.  
  822.         case BPF_JSET:
  823.             v &= b->s.k;
  824.             break;
  825.  
  826.         default:
  827.             abort();
  828.         }
  829.         if (JF(b) != JT(b))
  830.             done = 0;
  831.         if (v)
  832.             JF(b) = JT(b);
  833.         else
  834.             JT(b) = JF(b);
  835.     }
  836. }
  837.  
  838. /*
  839.  * Compute the symbolic value of expression of 's', and update
  840.  * anything it defines in the value table 'val'.  If 'alter' is true,
  841.  * do various optimizations.  This code would be cleaner if symbolic
  842.  * evaluation and code transformations weren't folded together.
  843.  */
  844. static void
  845. opt_stmt(s, val, alter)
  846.     struct stmt *s;
  847.     long val[];
  848.     int alter;
  849. {
  850.     int op;
  851.     long v;
  852.  
  853.     switch (s->code) {
  854.  
  855.     case BPF_LD|BPF_ABS|BPF_W:
  856.     case BPF_LD|BPF_ABS|BPF_H:
  857.     case BPF_LD|BPF_ABS|BPF_B:
  858.         v = F(s->code, s->k, 0L);
  859.         vstore(s, &val[A_ATOM], v, alter);
  860.         break;
  861.  
  862.     case BPF_LD|BPF_IND|BPF_W:
  863.     case BPF_LD|BPF_IND|BPF_H:
  864.     case BPF_LD|BPF_IND|BPF_B:
  865.         v = val[X_ATOM];
  866.         if (alter && vmap[v].is_const) {
  867.             s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
  868.             s->k += vmap[v].const_val;
  869.             v = F(s->code, s->k, 0L);
  870.             done = 0;
  871.         }
  872.         else
  873.             v = F(s->code, s->k, v);
  874.         vstore(s, &val[A_ATOM], v, alter);
  875.         break;
  876.  
  877.     case BPF_LD|BPF_LEN:
  878.         v = F(s->code, 0L, 0L);
  879.         vstore(s, &val[A_ATOM], v, alter);
  880.         break;
  881.  
  882.     case BPF_LD|BPF_IMM:
  883.         v = K(s->k);
  884.         vstore(s, &val[A_ATOM], v, alter);
  885.         break;
  886.  
  887.     case BPF_LDX|BPF_IMM:
  888.         v = K(s->k);
  889.         vstore(s, &val[X_ATOM], v, alter);
  890.         break;
  891.  
  892.     case BPF_LDX|BPF_MSH|BPF_B:
  893.         v = F(s->code, s->k, 0L);
  894.         vstore(s, &val[X_ATOM], v, alter);
  895.         break;
  896.  
  897.     case BPF_ALU|BPF_NEG:
  898.         if (alter && vmap[val[A_ATOM]].is_const) {
  899.             s->code = BPF_LD|BPF_IMM;
  900.             s->k = -vmap[val[A_ATOM]].const_val;
  901.             val[A_ATOM] = K(s->k);
  902.         }
  903.         else
  904.             val[A_ATOM] = F(s->code, val[A_ATOM], 0L);
  905.         break;
  906.  
  907.     case BPF_ALU|BPF_ADD|BPF_K:
  908.     case BPF_ALU|BPF_SUB|BPF_K:
  909.     case BPF_ALU|BPF_MUL|BPF_K:
  910.     case BPF_ALU|BPF_DIV|BPF_K:
  911.     case BPF_ALU|BPF_AND|BPF_K:
  912.     case BPF_ALU|BPF_OR|BPF_K:
  913.     case BPF_ALU|BPF_LSH|BPF_K:
  914.     case BPF_ALU|BPF_RSH|BPF_K:
  915.         op = BPF_OP(s->code);
  916.         if (alter) {
  917.             if (s->k == 0) {
  918.                 if (op == BPF_ADD || op == BPF_SUB ||
  919.                     op == BPF_LSH || op == BPF_RSH ||
  920.                     op == BPF_OR) {
  921.                     s->code = NOP;
  922.                     break;
  923.                 }
  924.                 if (op == BPF_MUL || op == BPF_AND) {
  925.                     s->code = BPF_LD|BPF_IMM;
  926.                     val[A_ATOM] = K(s->k);
  927.                     break;
  928.                 }
  929.             }
  930.             if (vmap[val[A_ATOM]].is_const) {
  931.                 fold_op(s, val[A_ATOM], K(s->k));
  932.                 val[A_ATOM] = K(s->k);
  933.                 break;
  934.             }
  935.         }
  936.         val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k));
  937.         break;
  938.  
  939.     case BPF_ALU|BPF_ADD|BPF_X:
  940.     case BPF_ALU|BPF_SUB|BPF_X:
  941.     case BPF_ALU|BPF_MUL|BPF_X:
  942.     case BPF_ALU|BPF_DIV|BPF_X:
  943.     case BPF_ALU|BPF_AND|BPF_X:
  944.     case BPF_ALU|BPF_OR|BPF_X:
  945.     case BPF_ALU|BPF_LSH|BPF_X:
  946.     case BPF_ALU|BPF_RSH|BPF_X:
  947.         op = BPF_OP(s->code);
  948.         if (alter && vmap[val[X_ATOM]].is_const) {
  949.             if (vmap[val[A_ATOM]].is_const) {
  950.                 fold_op(s, val[A_ATOM], val[X_ATOM]);
  951.                 val[A_ATOM] = K(s->k);
  952.             }
  953.             else {
  954.                 s->code = BPF_ALU|BPF_K|op;
  955.                 s->k = vmap[val[X_ATOM]].const_val;
  956.                 done = 0;
  957.                 val[A_ATOM] =
  958.                     F(s->code, val[A_ATOM], K(s->k));
  959.             }
  960.             break;
  961.         }
  962.         /*
  963.          * Check if we're doing something to an accumulator
  964.          * that is 0, and simplify.  This may not seem like
  965.          * much of a simplification but it could open up further
  966.          * optimizations.
  967.          * XXX We could also check for mul by 1, and -1, etc.
  968.          */
  969.         if (alter && vmap[val[A_ATOM]].is_const
  970.             && vmap[val[A_ATOM]].const_val == 0) {
  971.             if (op == BPF_ADD || op == BPF_OR ||
  972.                 op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) {
  973.                 s->code = BPF_MISC|BPF_TXA;
  974.                 vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  975.                 break;
  976.             }
  977.             else if (op == BPF_MUL || op == BPF_DIV ||
  978.                  op == BPF_AND) {
  979.                 s->code = BPF_LD|BPF_IMM;
  980.                 s->k = 0;
  981.                 vstore(s, &val[A_ATOM], K(s->k), alter);
  982.                 break;
  983.             }
  984.             else if (op == BPF_NEG) {
  985.                 s->code = NOP;
  986.                 break;
  987.             }
  988.         }
  989.         val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]);
  990.         break;
  991.  
  992.     case BPF_MISC|BPF_TXA:
  993.         vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  994.         break;
  995.  
  996.     case BPF_LD|BPF_MEM:
  997.         v = val[s->k];
  998.         if (alter && vmap[v].is_const) {
  999.             s->code = BPF_LD|BPF_IMM;
  1000.             s->k = vmap[v].const_val;
  1001.             done = 0;
  1002.         }
  1003.         vstore(s, &val[A_ATOM], v, alter);
  1004.         break;
  1005.  
  1006.     case BPF_MISC|BPF_TAX:
  1007.         vstore(s, &val[X_ATOM], val[A_ATOM], alter);
  1008.         break;
  1009.  
  1010.     case BPF_LDX|BPF_MEM:
  1011.         v = val[s->k];
  1012.         if (alter && vmap[v].is_const) {
  1013.             s->code = BPF_LDX|BPF_IMM;
  1014.             s->k = vmap[v].const_val;
  1015.             done = 0;
  1016.         }
  1017.         vstore(s, &val[X_ATOM], v, alter);
  1018.         break;
  1019.  
  1020.     case BPF_ST:
  1021.         vstore(s, &val[s->k], val[A_ATOM], alter);
  1022.         break;
  1023.  
  1024.     case BPF_STX:
  1025.         vstore(s, &val[s->k], val[X_ATOM], alter);
  1026.         break;
  1027.     }
  1028. }
  1029.  
  1030. static void
  1031. deadstmt(s, last)
  1032.     register struct stmt *s;
  1033.     register struct stmt *last[];
  1034. {
  1035.     register int atom;
  1036.  
  1037.     atom = atomuse(s);
  1038.     if (atom >= 0) {
  1039.         if (atom == AX_ATOM) {
  1040.             last[X_ATOM] = 0;
  1041.             last[A_ATOM] = 0;
  1042.         }
  1043.         else
  1044.             last[atom] = 0;
  1045.     }
  1046.     atom = atomdef(s);
  1047.     if (atom >= 0) {
  1048.         if (last[atom]) {
  1049.             done = 0;
  1050.             last[atom]->code = NOP;
  1051.         }
  1052.         last[atom] = s;
  1053.     }
  1054. }
  1055.  
  1056. static void
  1057. opt_deadstores(b)
  1058.     register struct block *b;
  1059. {
  1060.     register struct slist *s;
  1061.     register int atom;
  1062.     struct stmt *last[N_ATOMS];
  1063.  
  1064.     memset((char *)last, 0, sizeof last);
  1065.  
  1066.     for (s = b->stmts; s != 0; s = s->next)
  1067.         deadstmt(&s->s, last);
  1068.     deadstmt(&b->s, last);
  1069.  
  1070.     for (atom = 0; atom < N_ATOMS; ++atom)
  1071.         if (last[atom] && !ATOMELEM(b->out_use, atom)) {
  1072.             last[atom]->code = NOP;
  1073.             done = 0;
  1074.         }
  1075. }
  1076.  
  1077. static void
  1078. opt_blk(b, do_stmts)
  1079.     struct block *b;
  1080.     int do_stmts;
  1081. {
  1082.     struct slist *s;
  1083.     struct edge *p;
  1084.     int i;
  1085.     long aval;
  1086.  
  1087.     /*
  1088.      * Initialize the atom values.
  1089.      * If we have no predecessors, everything is undefined.
  1090.      * Otherwise, we inherent our values from our predecessors.
  1091.      * If any register has an ambiguous value (i.e. control paths are
  1092.      * merging) give it the undefined value of 0.
  1093.      */
  1094.     p = b->in_edges;
  1095.     if (p == 0)
  1096.         memset((char *)b->val, 0, sizeof(b->val));
  1097.     else {
  1098.         memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val));
  1099.         while ((p = p->next) != NULL) {
  1100.             for (i = 0; i < N_ATOMS; ++i)
  1101.                 if (b->val[i] != p->pred->val[i])
  1102.                     b->val[i] = 0;
  1103.         }
  1104.     }
  1105.     aval = b->val[A_ATOM];
  1106.     for (s = b->stmts; s; s = s->next)
  1107.         opt_stmt(&s->s, b->val, do_stmts);
  1108.  
  1109.     /*
  1110.      * This is a special case: if we don't use anything from this
  1111.      * block, and we load the accumulator with value that is
  1112.      * already there, eliminate all the statements.
  1113.      */
  1114.     if (do_stmts && b->out_use == 0 && aval != 0 &&
  1115.         b->val[A_ATOM] == aval)
  1116.         b->stmts = 0;
  1117.     else {
  1118.         opt_peep(b);
  1119.         opt_deadstores(b);
  1120.     }
  1121.     /*
  1122.      * Set up values for branch optimizer.
  1123.      */
  1124.     if (BPF_SRC(b->s.code) == BPF_K)
  1125.         b->oval = K(b->s.k);
  1126.     else
  1127.         b->oval = b->val[X_ATOM];
  1128.     b->et.code = b->s.code;
  1129.     b->ef.code = -b->s.code;
  1130. }
  1131.  
  1132. /*
  1133.  * Return true if any register that is used on exit from 'succ', has
  1134.  * an exit value that is different from the corresponding exit value
  1135.  * from 'b'.
  1136.  */
  1137. static int
  1138. use_conflict(b, succ)
  1139.     struct block *b, *succ;
  1140. {
  1141.     int atom;
  1142.     atomset use = succ->out_use;
  1143.  
  1144.     if (use == 0)
  1145.         return 0;
  1146.  
  1147.     for (atom = 0; atom < N_ATOMS; ++atom)
  1148.         if (ATOMELEM(use, atom))
  1149.             if (b->val[atom] != succ->val[atom])
  1150.                 return 1;
  1151.     return 0;
  1152. }
  1153.  
  1154. static struct block *
  1155. fold_edge(child, ep)
  1156.     struct block *child;
  1157.     struct edge *ep;
  1158. {
  1159.     int sense;
  1160.     int aval0, aval1, oval0, oval1;
  1161.     int code = ep->code;
  1162.  
  1163.     if (code < 0) {
  1164.         code = -code;
  1165.         sense = 0;
  1166.     } else
  1167.         sense = 1;
  1168.  
  1169.     if (child->s.code != code)
  1170.         return 0;
  1171.  
  1172.     aval0 = child->val[A_ATOM];
  1173.     oval0 = child->oval;
  1174.     aval1 = ep->pred->val[A_ATOM];
  1175.     oval1 = ep->pred->oval;
  1176.  
  1177.     if (aval0 != aval1)
  1178.         return 0;
  1179.  
  1180.     if (oval0 == oval1)
  1181.         /*
  1182.          * The operands are identical, so the
  1183.          * result is true if a true branch was
  1184.          * taken to get here, otherwise false.
  1185.          */
  1186.         return sense ? JT(child) : JF(child);
  1187.  
  1188.     if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K))
  1189.         /*
  1190.          * At this point, we only know the comparison if we
  1191.          * came down the true branch, and it was an equality
  1192.          * comparison with a constant.  We rely on the fact that
  1193.          * distinct constants have distinct value numbers.
  1194.          */
  1195.         return JF(child);
  1196.  
  1197.     return 0;
  1198. }
  1199.  
  1200. static void
  1201. opt_j(ep)
  1202.     struct edge *ep;
  1203. {
  1204.     register int i, k;
  1205.     register struct block *target;
  1206.  
  1207.     if (JT(ep->succ) == 0)
  1208.         return;
  1209.  
  1210.     if (JT(ep->succ) == JF(ep->succ)) {
  1211.         /*
  1212.          * Common branch targets can be eliminated, provided
  1213.          * there is no data dependency.
  1214.          */
  1215.         if (!use_conflict(ep->pred, ep->succ->et.succ)) {
  1216.             done = 0;
  1217.             ep->succ = JT(ep->succ);
  1218.         }
  1219.     }
  1220.     /*
  1221.      * For each edge dominator that matches the successor of this
  1222.      * edge, promote the edge successor to the its grandchild.
  1223.      *
  1224.      * XXX We violate the set abstraction here in favor a reasonably
  1225.      * efficient loop.
  1226.      */
  1227.  top:
  1228.     for (i = 0; i < edgewords; ++i) {
  1229.         register u_long x = ep->edom[i];
  1230.  
  1231.         while (x != 0) {
  1232.             k = ffs(x) - 1;
  1233.             x &=~ (1 << k);
  1234.             k += i * BITS_PER_WORD;
  1235.  
  1236.             target = fold_edge(ep->succ, edges[k]);
  1237.             /*
  1238.              * Check that there is no data dependency between
  1239.              * nodes that will be violated if we move the edge.
  1240.              */
  1241.             if (target != 0 && !use_conflict(ep->pred, target)) {
  1242.                 done = 0;
  1243.                 ep->succ = target;
  1244.                 if (JT(target) != 0)
  1245.                     /*
  1246.                      * Start over unless we hit a leaf.
  1247.                      */
  1248.                     goto top;
  1249.                 return;
  1250.             }
  1251.         }
  1252.     }
  1253. }
  1254.  
  1255.  
  1256. static void
  1257. or_pullup(b)
  1258.     struct block *b;
  1259. {
  1260.     int val, at_top;
  1261.     struct block *pull;
  1262.     struct block **diffp, **samep;
  1263.     struct edge *ep;
  1264.  
  1265.     ep = b->in_edges;
  1266.     if (ep == 0)
  1267.         return;
  1268.  
  1269.     /*
  1270.      * Make sure each predecessor loads the same value.
  1271.      * XXX why?
  1272.      */
  1273.     val = ep->pred->val[A_ATOM];
  1274.     for (ep = ep->next; ep != 0; ep = ep->next)
  1275.         if (val != ep->pred->val[A_ATOM])
  1276.             return;
  1277.  
  1278.     if (JT(b->in_edges->pred) == b)
  1279.         diffp = &JT(b->in_edges->pred);
  1280.     else
  1281.         diffp = &JF(b->in_edges->pred);
  1282.  
  1283.     at_top = 1;
  1284.     while (1) {
  1285.         if (*diffp == 0)
  1286.             return;
  1287.  
  1288.         if (JT(*diffp) != JT(b))
  1289.             return;
  1290.  
  1291.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1292.             return;
  1293.  
  1294.         if ((*diffp)->val[A_ATOM] != val)
  1295.             break;
  1296.  
  1297.         diffp = &JF(*diffp);
  1298.         at_top = 0;
  1299.     }
  1300.     samep = &JF(*diffp);
  1301.     while (1) {
  1302.         if (*samep == 0)
  1303.             return;
  1304.  
  1305.         if (JT(*samep) != JT(b))
  1306.             return;
  1307.  
  1308.         if (!SET_MEMBER((*samep)->dom, b->id))
  1309.             return;
  1310.  
  1311.         if ((*samep)->val[A_ATOM] == val)
  1312.             break;
  1313.  
  1314.         /* XXX Need to check that there are no data dependencies
  1315.            between dp0 and dp1.  Currently, the code generator
  1316.            will not produce such dependencies. */
  1317.         samep = &JF(*samep);
  1318.     }
  1319. #ifdef notdef
  1320.     /* XXX This doesn't cover everything. */
  1321.     for (i = 0; i < N_ATOMS; ++i)
  1322.         if ((*samep)->val[i] != pred->val[i])
  1323.             return;
  1324. #endif
  1325.     /* Pull up the node. */
  1326.     pull = *samep;
  1327.     *samep = JF(pull);
  1328.     JF(pull) = *diffp;
  1329.  
  1330.     /*
  1331.      * At the top of the chain, each predecessor needs to point at the
  1332.      * pulled up node.  Inside the chain, there is only one predecessor
  1333.      * to worry about.
  1334.      */
  1335.     if (at_top) {
  1336.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1337.             if (JT(ep->pred) == b)
  1338.                 JT(ep->pred) = pull;
  1339.             else
  1340.                 JF(ep->pred) = pull;
  1341.         }
  1342.     }
  1343.     else
  1344.         *diffp = pull;
  1345.  
  1346.     done = 0;
  1347. }
  1348.  
  1349. static void
  1350. and_pullup(b)
  1351.     struct block *b;
  1352. {
  1353.     int val, at_top;
  1354.     struct block *pull;
  1355.     struct block **diffp, **samep;
  1356.     struct edge *ep;
  1357.  
  1358.     ep = b->in_edges;
  1359.     if (ep == 0)
  1360.         return;
  1361.  
  1362.     /*
  1363.      * Make sure each predecessor loads the same value.
  1364.      */
  1365.     val = ep->pred->val[A_ATOM];
  1366.     for (ep = ep->next; ep != 0; ep = ep->next)
  1367.         if (val != ep->pred->val[A_ATOM])
  1368.             return;
  1369.  
  1370.     if (JT(b->in_edges->pred) == b)
  1371.         diffp = &JT(b->in_edges->pred);
  1372.     else
  1373.         diffp = &JF(b->in_edges->pred);
  1374.  
  1375.     at_top = 1;
  1376.     while (1) {
  1377.         if (*diffp == 0)
  1378.             return;
  1379.  
  1380.         if (JF(*diffp) != JF(b))
  1381.             return;
  1382.  
  1383.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1384.             return;
  1385.  
  1386.         if ((*diffp)->val[A_ATOM] != val)
  1387.             break;
  1388.  
  1389.         diffp = &JT(*diffp);
  1390.         at_top = 0;
  1391.     }
  1392.     samep = &JT(*diffp);
  1393.     while (1) {
  1394.         if (*samep == 0)
  1395.             return;
  1396.  
  1397.         if (JF(*samep) != JF(b))
  1398.             return;
  1399.  
  1400.         if (!SET_MEMBER((*samep)->dom, b->id))
  1401.             return;
  1402.  
  1403.         if ((*samep)->val[A_ATOM] == val)
  1404.             break;
  1405.  
  1406.         /* XXX Need to check that there are no data dependencies
  1407.            between diffp and samep.  Currently, the code generator
  1408.            will not produce such dependencies. */
  1409.         samep = &JT(*samep);
  1410.     }
  1411. #ifdef notdef
  1412.     /* XXX This doesn't cover everything. */
  1413.     for (i = 0; i < N_ATOMS; ++i)
  1414.         if ((*samep)->val[i] != pred->val[i])
  1415.             return;
  1416. #endif
  1417.     /* Pull up the node. */
  1418.     pull = *samep;
  1419.     *samep = JT(pull);
  1420.     JT(pull) = *diffp;
  1421.  
  1422.     /*
  1423.      * At the top of the chain, each predecessor needs to point at the
  1424.      * pulled up node.  Inside the chain, there is only one predecessor
  1425.      * to worry about.
  1426.      */
  1427.     if (at_top) {
  1428.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1429.             if (JT(ep->pred) == b)
  1430.                 JT(ep->pred) = pull;
  1431.             else
  1432.                 JF(ep->pred) = pull;
  1433.         }
  1434.     }
  1435.     else
  1436.         *diffp = pull;
  1437.  
  1438.     done = 0;
  1439. }
  1440.  
  1441. static void
  1442. opt_blks(root, do_stmts)
  1443.     struct block *root;
  1444.     int do_stmts;
  1445. {
  1446.     int i, maxlevel;
  1447.     struct block *p;
  1448.  
  1449.     init_val();
  1450.     maxlevel = root->level;
  1451.     for (i = maxlevel; i >= 0; --i)
  1452.         for (p = levels[i]; p; p = p->link)
  1453.             opt_blk(p, do_stmts);
  1454.  
  1455.     if (do_stmts)
  1456.         /*
  1457.          * No point trying to move branches; it can't possibly
  1458.          * make a difference at this point.
  1459.          */
  1460.         return;
  1461.  
  1462.     for (i = 1; i <= maxlevel; ++i) {
  1463.         for (p = levels[i]; p; p = p->link) {
  1464.             opt_j(&p->et);
  1465.             opt_j(&p->ef);
  1466.         }
  1467.     }
  1468.     for (i = 1; i <= maxlevel; ++i) {
  1469.         for (p = levels[i]; p; p = p->link) {
  1470.             or_pullup(p);
  1471.             and_pullup(p);
  1472.         }
  1473.     }
  1474. }
  1475.  
  1476. static inline void
  1477. link_inedge(parent, child)
  1478.     struct edge *parent;
  1479.     struct block *child;
  1480. {
  1481.     parent->next = child->in_edges;
  1482.     child->in_edges = parent;
  1483. }
  1484.  
  1485. static void
  1486. find_inedges(root)
  1487.     struct block *root;
  1488. {
  1489.     int i;
  1490.     struct block *b;
  1491.  
  1492.     for (i = 0; i < n_blocks; ++i)
  1493.         blocks[i]->in_edges = 0;
  1494.  
  1495.     /*
  1496.      * Traverse the graph, adding each edge to the predecessor
  1497.      * list of its successors.  Skip the leaves (i.e. level 0).
  1498.      */
  1499.     for (i = root->level; i > 0; --i) {
  1500.         for (b = levels[i]; b != 0; b = b->link) {
  1501.             link_inedge(&b->et, JT(b));
  1502.             link_inedge(&b->ef, JF(b));
  1503.         }
  1504.     }
  1505. }
  1506.  
  1507. static void
  1508. opt_root(b)
  1509.     struct block **b;
  1510. {
  1511.     struct slist *tmp, *s;
  1512.  
  1513.     s = (*b)->stmts;
  1514.     (*b)->stmts = 0;
  1515.     while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
  1516.         *b = JT(*b);
  1517.  
  1518.     tmp = (*b)->stmts;
  1519.     if (tmp != 0)
  1520.         sappend(s, tmp);
  1521.     (*b)->stmts = s;
  1522. }
  1523.  
  1524. static void
  1525. opt_loop(root, do_stmts)
  1526.     struct block *root;
  1527.     int do_stmts;
  1528. {
  1529.  
  1530. #ifdef BDEBUG
  1531.     if (dflag > 1)
  1532.         opt_dump(root);
  1533. #endif
  1534.     do {
  1535.         done = 1;
  1536.         find_levels(root);
  1537.         find_dom(root);
  1538.         find_closure(root);
  1539.         find_inedges(root);
  1540.         find_ud(root);
  1541.         find_edom(root);
  1542.         opt_blks(root, do_stmts);
  1543. #ifdef BDEBUG
  1544.         if (dflag > 1)
  1545.             opt_dump(root);
  1546. #endif
  1547.     } while (!done);
  1548. }
  1549.  
  1550. /*
  1551.  * Optimize the filter code in its dag representation.
  1552.  */
  1553. void
  1554. bpf_optimize(rootp)
  1555.     struct block **rootp;
  1556. {
  1557.     struct block *root;
  1558.  
  1559.     root = *rootp;
  1560.  
  1561.     opt_init(root);
  1562.     opt_loop(root, 0);
  1563.     opt_loop(root, 1);
  1564.     intern_blocks(root);
  1565.     opt_root(rootp);
  1566.     opt_cleanup();
  1567. }
  1568.  
  1569. static void
  1570. make_marks(p)
  1571.     struct block *p;
  1572. {
  1573.     if (!isMarked(p)) {
  1574.         Mark(p);
  1575.         if (BPF_CLASS(p->s.code) != BPF_RET) {
  1576.             make_marks(JT(p));
  1577.             make_marks(JF(p));
  1578.         }
  1579.     }
  1580. }
  1581.  
  1582. /*
  1583.  * Mark code array such that isMarked(i) is true
  1584.  * only for nodes that are alive.
  1585.  */
  1586. static void
  1587. mark_code(p)
  1588.     struct block *p;
  1589. {
  1590.     cur_mark += 1;
  1591.     make_marks(p);
  1592. }
  1593.  
  1594. /*
  1595.  * True iff the two stmt lists load the same value from the packet into
  1596.  * the accumulator.
  1597.  */
  1598. static int
  1599. eq_slist(x, y)
  1600.     struct slist *x, *y;
  1601. {
  1602.     while (1) {
  1603.         while (x && x->s.code == NOP)
  1604.             x = x->next;
  1605.         while (y && y->s.code == NOP)
  1606.             y = y->next;
  1607.         if (x == 0)
  1608.             return y == 0;
  1609.         if (y == 0)
  1610.             return x == 0;
  1611.         if (x->s.code != y->s.code || x->s.k != y->s.k)
  1612.             return 0;
  1613.         x = x->next;
  1614.         y = y->next;
  1615.     }
  1616. }
  1617.  
  1618. static inline int
  1619. eq_blk(b0, b1)
  1620.     struct block *b0, *b1;
  1621. {
  1622.     if (b0->s.code == b1->s.code &&
  1623.         b0->s.k == b1->s.k &&
  1624.         b0->et.succ == b1->et.succ &&
  1625.         b0->ef.succ == b1->ef.succ)
  1626.         return eq_slist(b0->stmts, b1->stmts);
  1627.     return 0;
  1628. }
  1629.  
  1630. static void
  1631. intern_blocks(root)
  1632.     struct block *root;
  1633. {
  1634.     struct block *p;
  1635.     int i, j;
  1636.     int done;
  1637.  top:
  1638.     done = 1;
  1639.     for (i = 0; i < n_blocks; ++i)
  1640.         blocks[i]->link = 0;
  1641.  
  1642.     mark_code(root);
  1643.  
  1644.     for (i = n_blocks - 1; --i >= 0; ) {
  1645.         if (!isMarked(blocks[i]))
  1646.             continue;
  1647.         for (j = i + 1; j < n_blocks; ++j) {
  1648.             if (!isMarked(blocks[j]))
  1649.                 continue;
  1650.             if (eq_blk(blocks[i], blocks[j])) {
  1651.                 blocks[i]->link = blocks[j]->link ?
  1652.                     blocks[j]->link : blocks[j];
  1653.                 break;
  1654.             }
  1655.         }
  1656.     }
  1657.     for (i = 0; i < n_blocks; ++i) {
  1658.         p = blocks[i];
  1659.         if (JT(p) == 0)
  1660.             continue;
  1661.         if (JT(p)->link) {
  1662.             done = 0;
  1663.             JT(p) = JT(p)->link;
  1664.         }
  1665.         if (JF(p)->link) {
  1666.             done = 0;
  1667.             JF(p) = JF(p)->link;
  1668.         }
  1669.     }
  1670.     if (!done)
  1671.         goto top;
  1672. }
  1673.  
  1674. static void
  1675. opt_cleanup()
  1676. {
  1677.     free((void *)vnode_base);
  1678.     free((void *)vmap);
  1679.     free((void *)edges);
  1680.     free((void *)space);
  1681.     free((void *)levels);
  1682.     free((void *)blocks);
  1683. }
  1684.  
  1685. /*
  1686.  * Return the number of stmts in 's'.
  1687.  */
  1688. static int
  1689. slength(s)
  1690.     struct slist *s;
  1691. {
  1692.     int n = 0;
  1693.  
  1694.     for (; s; s = s->next)
  1695.         if (s->s.code != NOP)
  1696.             ++n;
  1697.     return n;
  1698. }
  1699.  
  1700. /*
  1701.  * Return the number of nodes reachable by 'p'.
  1702.  * All nodes should be initially unmarked.
  1703.  */
  1704. static int
  1705. count_blocks(p)
  1706.     struct block *p;
  1707. {
  1708.     if (p == 0 || isMarked(p))
  1709.         return 0;
  1710.     Mark(p);
  1711.     return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
  1712. }
  1713.  
  1714. /*
  1715.  * Do a depth first search on the flow graph, numbering the
  1716.  * the basic blocks, and entering them into the 'blocks' array.`
  1717.  */
  1718. static void
  1719. number_blks_r(p)
  1720.     struct block *p;
  1721. {
  1722.     int n;
  1723.  
  1724.     if (p == 0 || isMarked(p))
  1725.         return;
  1726.  
  1727.     Mark(p);
  1728.     n = n_blocks++;
  1729.     p->id = n;
  1730.     blocks[n] = p;
  1731.  
  1732.     number_blks_r(JT(p));
  1733.     number_blks_r(JF(p));
  1734. }
  1735.  
  1736. /*
  1737.  * Return the number of stmts in the flowgraph reachable by 'p'.
  1738.  * The nodes should be unmarked before calling.
  1739.  */
  1740. static int
  1741. count_stmts(p)
  1742.     struct block *p;
  1743. {
  1744.     int n;
  1745.  
  1746.     if (p == 0 || isMarked(p))
  1747.         return 0;
  1748.     Mark(p);
  1749.     n = count_stmts(JT(p)) + count_stmts(JF(p));
  1750.     return slength(p->stmts) + n + 1;
  1751. }
  1752.  
  1753. /*
  1754.  * Allocate memory.  All allocation is done before optimization
  1755.  * is begun.  A linear bound on the size of all data structures is computed
  1756.  * from the total number of blocks and/or statements.
  1757.  */
  1758. static void
  1759. opt_init(root)
  1760.     struct block *root;
  1761. {
  1762.     u_long *p;
  1763.     int i, n, max_stmts;
  1764.  
  1765.     /*
  1766.      * First, count the blocks, so we can malloc an array to map
  1767.      * block number to block.  Then, put the blocks into the array.
  1768.      */
  1769.     unMarkAll();
  1770.     n = count_blocks(root);
  1771.     blocks = (struct block **)malloc(n * sizeof(*blocks));
  1772.     unMarkAll();
  1773.     n_blocks = 0;
  1774.     number_blks_r(root);
  1775.  
  1776.     n_edges = 2 * n_blocks;
  1777.     edges = (struct edge **)malloc(n_edges * sizeof(*edges));
  1778.  
  1779.     /*
  1780.      * The number of levels is bounded by the number of nodes.
  1781.      */
  1782.     levels = (struct block **)malloc(n_blocks * sizeof(*levels));
  1783.  
  1784.     edgewords = n_edges / (8 * sizeof(u_long)) + 1;
  1785.     nodewords = n_blocks / (8 * sizeof(u_long)) + 1;
  1786.  
  1787.     /* XXX */
  1788.     space = (u_long *)malloc(2 * n_blocks * nodewords * sizeof(*space)
  1789.                  + n_edges * edgewords * sizeof(*space));
  1790.     p = space;
  1791.     all_dom_sets = p;
  1792.     for (i = 0; i < n; ++i) {
  1793.         blocks[i]->dom = p;
  1794.         p += nodewords;
  1795.     }
  1796.     all_closure_sets = p;
  1797.     for (i = 0; i < n; ++i) {
  1798.         blocks[i]->closure = p;
  1799.         p += nodewords;
  1800.     }
  1801.     all_edge_sets = p;
  1802.     for (i = 0; i < n; ++i) {
  1803.         register struct block *b = blocks[i];
  1804.  
  1805.         b->et.edom = p;
  1806.         p += edgewords;
  1807.         b->ef.edom = p;
  1808.         p += edgewords;
  1809.         b->et.id = i;
  1810.         edges[i] = &b->et;
  1811.         b->ef.id = n_blocks + i;
  1812.         edges[n_blocks + i] = &b->ef;
  1813.         b->et.pred = b;
  1814.         b->ef.pred = b;
  1815.     }
  1816.     max_stmts = 0;
  1817.     for (i = 0; i < n; ++i)
  1818.         max_stmts += slength(blocks[i]->stmts) + 1;
  1819.     /*
  1820.      * We allocate at most 3 value numbers per statement,
  1821.      * so this is an upper bound on the number of valnodes
  1822.      * we'll need.
  1823.      */
  1824.     maxval = 3 * max_stmts;
  1825.     vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
  1826.     vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
  1827. }
  1828.  
  1829. /*
  1830.  * Some pointers used to convert the basic block form of the code,
  1831.  * into the array form that BPF requires.  'fstart' will point to
  1832.  * the malloc'd array while 'ftail' is used during the recursive traversal.
  1833.  */
  1834. static struct bpf_insn *fstart;
  1835. static struct bpf_insn *ftail;
  1836.  
  1837. #ifdef BDEBUG
  1838. int bids[1000];
  1839. #endif
  1840.  
  1841. static void
  1842. convert_code_r(p)
  1843.     struct block *p;
  1844. {
  1845.     struct bpf_insn *dst;
  1846.     struct slist *src;
  1847.     int slen;
  1848.     u_int off;
  1849.  
  1850.     if (p == 0 || isMarked(p))
  1851.         return;
  1852.     Mark(p);
  1853.  
  1854.     convert_code_r(JF(p));
  1855.     convert_code_r(JT(p));
  1856.  
  1857.     slen = slength(p->stmts);
  1858.     dst = ftail -= slen + 1;
  1859.  
  1860.     p->offset = dst - fstart;
  1861.  
  1862.     for (src = p->stmts; src; src = src->next) {
  1863.         if (src->s.code == NOP)
  1864.             continue;
  1865.         dst->code = (u_short)src->s.code;
  1866.         dst->k = src->s.k;
  1867.         ++dst;
  1868.     }
  1869. #ifdef BDEBUG
  1870.     bids[dst - fstart] = p->id + 1;
  1871. #endif
  1872.     dst->code = (u_short)p->s.code;
  1873.     dst->k = p->s.k;
  1874.     if (JT(p)) {
  1875.         off = JT(p)->offset - (p->offset + slen) - 1;
  1876.         if (off >= 256)
  1877.             bpf_error("long jumps not supported");
  1878.         dst->jt = off;
  1879.         off = JF(p)->offset - (p->offset + slen) - 1;
  1880.         if (off >= 256)
  1881.             bpf_error("long jumps not supported");
  1882.         dst->jf = off;
  1883.     }
  1884. }
  1885.  
  1886.  
  1887. /*
  1888.  * Convert flowgraph intermediate representation to the
  1889.  * BPF array representation.  Set *lenp to the number of instructions.
  1890.  */
  1891. struct bpf_insn *
  1892. icode_to_fcode(root, lenp)
  1893.     struct block *root;
  1894.     int *lenp;
  1895. {
  1896.     int n;
  1897.     struct bpf_insn *fp;
  1898.  
  1899.     unMarkAll();
  1900.     n = *lenp = count_stmts(root);
  1901.  
  1902.     fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
  1903.     memset((char *)fp, 0, sizeof(*fp) * n);
  1904.     fstart = fp;
  1905.     ftail = fp + n;
  1906.  
  1907.     unMarkAll();
  1908.     convert_code_r(root);
  1909.  
  1910.     return fp;
  1911. }
  1912.  
  1913. #ifdef BDEBUG
  1914. opt_dump(root)
  1915.     struct block *root;
  1916. {
  1917.     struct bpf_program f;
  1918.  
  1919.     memset(bids, 0, sizeof bids);
  1920.     f.bf_insns = icode_to_fcode(root, &f.bf_len);
  1921.     bpf_dump(&f, 1);
  1922.     putchar('\n');
  1923.     free((char *)f.bf_insns);
  1924. }
  1925. #endif
  1926.